/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 22652
 * Date: 2024-06-16
 * Time: 15:37
 */
public class test_3 {

    public static void main(String[] args) {
        int[] arr = {-2, 11, -4, 13, -5, -2};
        System.out.println(maxSubSum(arr, 0, arr.length - 1));
    }

    private static int max(int a, int b, int c) {
        if (a < b) {
            a = b;
        }
        if (a > c)
            return a;
        else
            return c;
    }

    private static int maxSubSum(int[] arr, int left, int right) {
        int max_left_sum, max_right_sum;
        int max_left_border_sum = 0, max_right_border_sum = 0;

        if (left == right) {
            if (arr[left] > 0)
                return arr[left];
            else {
                return 0;
            }
        }
        int mid = (left + right) / 2;
        max_left_sum = maxSubSum(arr, left, mid);
        max_right_sum = maxSubSum(arr, mid + 1, right);
        int r = 0;
        int l = 0;
        for (int i = mid; i >= left; i--) {
            l += arr[i];
            if (max_left_border_sum <= l) {
                max_left_border_sum = l;
            }
        }
        for (int i = mid+1; i <= right; i++) {
            r += arr[i];
            if (max_right_border_sum <= r) {
                max_right_border_sum = r;
            }
        }
        return max(max_left_sum, max_right_sum, max_left_border_sum + max_right_border_sum);
    }
}
